#include <iostream>
#include <vector>
using namespace std;
class Solution {
public:
    vector<int> rearrangeBarcodes(vector<int>& barcodes) {
        int n = barcodes.size(), j = 0;
        for (int i = 0; i < n - 1; i++) {
            if (barcodes[i] != barcodes[i + 1]) continue;
            j = i + 2;
            while (barcodes[i] == barcodes[j]) j++;
            if (j == n) break;
            swap(barcodes[i + 1], barcodes[j]);
        }
        if (j < n) return barcodes;
        for (int i = n; i-- > 1;) {
            if (barcodes[i] != barcodes[i - 1]) continue;
            j = i - 2;
            while (barcodes[i] == barcodes[j]) j--;
            swap(barcodes[i - 1], barcodes[j]);
        }
        return barcodes;
    }
};
int main()
{
	return 0;
}